package com.LeetCode.dp.shares;

import org.junit.Test;

/**
 * 买卖股票的最佳时机 Ⅲ 有两次买卖机会
 */
public class shares_3 {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int max_k = 2;
        // 第 i 天 , 最大交易次数, 是否买入 0 : 1 ?
        int[][][] dp = new int[len][max_k+1][2];

        dp[0][2][0] = 0;
        dp[0][2][1] = -prices[0];
        dp[0][1][0] = 0;
        dp[0][1][1] = -prices[0];
        for(int i = 0; i<len; i++){
            for(int k = max_k; k>=1; i--){
                if(i - 1 == -1) continue;
                dp[i][k][0] = Math.max(dp[i-1][k][1] + prices[1] , dp[i-1][k][0]);
                dp[i][k][1] = Math.max(dp[i-1][k-1][0] - prices[i] , dp[i-1][k][1]);
            }
        }

        return dp[len - 1][max_k][0];
    }

    public int maxProfit_withTwoDimension(int[] prices){
        if(prices.length == 0) return 0;
        int len = prices.length;
        // 天数 , 状态 ： 0 没买， 1 第一次买， 2 第一次卖， 3 第二次买 4 第二次卖
        int[][] dp = new int[len][5];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for(int i = 1; i<len; i++){
            dp[i][0] = 0;
            dp[i][1] = Math.max(dp[i-1][0] - prices[i], dp[i-1][1]);
            dp[i][2] = Math.max(dp[i-1][1] + prices[i] , dp[i-1][2]);
            dp[i][3] = Math.max(dp[i-1][2] - prices[i] , dp[i-1][3]);
            dp[i][4] = Math.max(dp[i-1][3] + prices[i] , dp[i-1][4]);
        }
        return Math.max(dp[len-1][2] , dp[len-1][4]);
    }

    /**
     * 可以发现，方法二中的递推，只跟上一个值有关，所以可以优化空间
     */
    public int maxProfit_withOneDimension(int[] prices){
        if (prices.length == 0) return 0;
        int len = prices.length;
        int[] dp = new int[5];
        dp[0] = 0;
        dp[1] = -prices[0];
        dp[2] = Integer.MIN_VALUE;
        dp[3] = Integer.MIN_VALUE;
        dp[4] = Integer.MIN_VALUE;
        for(int i = 1; i<len; i++){
            dp[0] = 0;
            dp[1] = Math.max(dp[0] - prices[i] , dp[1]);
            dp[2] = Math.max(dp[1] + prices[i] , dp[2]);
            dp[3] = Math.max(dp[0] - prices[i] , dp[3]);
            dp[4] = Math.max(dp[3] + prices[i] , dp[4]);
        }
        return Math.max(dp[2],dp[4]);
    }

    @Test
    public void test(){

    }

}
